5. 最长回文子串
5. 最长回文子串
- 暴力解法
- 动态规划
- 马拉车算法,没仔细看
动态规划算法:
func longestPalindrome(s string) string {
return dynamic(s)
}
func dynamic(s string) string {
dp := make([][]bool, len(s))
for i := range dp {
dp[i] = make([]bool, len(s))
dp[i][i] = true
}
ret := s[0:1]
mxLen := 1
for j := 1; j < len(s); j++ {
for i := 0; i<j; i++ {
if s[i] == s[j] {
if j-i < 3 {
dp[i][j] = true
} else {
dp[i][j] = dp[i+1][j-1]
}
if dp[i][j] && j-i+1 > mxLen {
mxLen = j-i+1
ret = s[i:j+1]
}
} else {
dp[i][j] = false
}
}
}
return ret
}
初始化:
填表格,对角线,也就是 i=j 时,单个字符,都是回文串,设置为 true dp[i][i] = true
遍历顺序:
因为初始化的是对角线,也就是如图所示:
图中对角线坐标写错了,应该是 [0,0] [1,1] [2,2] [3,3]
如果按照平常的顺序,这么写代码遍历
for i := 0; i < len(s); i++ {
for j := i+1; j<len(s); j++ {
...
}
}
那么会有如图所示的问题,[0,3]
会因为需要 [1,2]
的结果从而导致无法推算出正确的结果
所以需要这么遍历,就能够使用到上一列的数据
本站总访问量次 本站访客数人次 本文总阅读量次